package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;

import java.util.HashMap;

/**
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/">
 * 3. 无重复字符的最长子串
 * </a>
 */
public class LeetCode3 {
    public static class Solution {
        public int lengthOfLongestSubstring(String s) {
            final HashMap<Character, Integer> map = new HashMap<>();
            int i = 0;
            int j = 0;
            int maxLength = 0;

            while (j < s.length()) {
                final char ch = s.charAt(j);
                if (map.containsKey(ch)) {
                    final int k = map.get(ch) + 1;
                    for (; i < k; i++) {
                        map.remove(s.charAt(i));
                    }
                }
                maxLength = Math.max(j - i + 1, maxLength);
                map.put(ch, j);
                j++;
            }
            return maxLength;
        }
    }

    public static void main(String[] args) {
        final Solution solution = new Solution();

        Assertions.assertEquals(2, solution.lengthOfLongestSubstring("abba"));
        Assertions.assertEquals(0, solution.lengthOfLongestSubstring(""));
        Assertions.assertEquals(6, solution.lengthOfLongestSubstring("abcadef"));
        Assertions.assertEquals(3, solution.lengthOfLongestSubstring("abcabcbb"));
        Assertions.assertEquals(1, solution.lengthOfLongestSubstring("bbbbb"));
        Assertions.assertEquals(3, solution.lengthOfLongestSubstring("pwwkew"));
    }
}
